package codingforgreat.lchot150;

import java.util.*;

public class Lc131 {
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        List<String> path = new ArrayList<>();
        if (s == null || s.length() < 2) {
            path.add(s);
            res.add(path);
            return res;
        }
        char[] str = s.toCharArray();
        boolean[][] checkMap = createCheckMap(str);

        //s , i , j ,         [][] path
        process(s, 0, 1, checkMap, path, res);
        return res;
    }
    public void process(String s,int i,int j,boolean[][] checkMap, List<String> path, List<List<String>> res){
        if(j == s.length()){
            if(checkMap[i][j - 1] ){
                path.add(s.substring(i,j));
                res.add(new ArrayList<>(path));
                path.remove(path.size() - 1);
            }
        }else{
            if(checkMap[i][j - 1]  ){
                path.add(s.substring(i,j));
                process(s,j,j + 1,checkMap,path,res);
                path.remove(path.size() - 1);
            }
            process(s,i,j + 1,checkMap,path,res);
        }
    }
    public boolean[][] createCheckMap(char[] str){
        boolean[][] res = new boolean[str.length][str.length];
        for(int i = 0;i < str.length - 1;i++){
            res[i][i] = true;
            res[i][i + 1] = str[i] == str[i + 1] ;
        }
        int N = str.length;
        res[N - 1][N - 1] = true;
        for(int i = N - 3;i >= 0;i--){
            for(int j = i + 2;j < N;j++){
                res[i][j] = str[i] == str[j] && res[i + 1][j - 1];
            }
        }
        return res;
    }
}
